package queue

import "sync"

// 用两个栈实现一个队列

type StackQueue struct {
	in  *LinkedListStack
	out *LinkedListStack
	mu  sync.Mutex
}

func NewQueue() *StackQueue {
	return &StackQueue{
		in:  NewLinkedListStack(),
		out: NewLinkedListStack(),
	}
}

func (q *StackQueue) Push(v interface{}) bool {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.out.IsEmpty() {
		q.in.Push(v)
		return true
	}
	return false
}

func (q *StackQueue) Pop() interface{} {
	q.mu.Lock()
	defer q.mu.Unlock()
	if q.out.IsEmpty() {
		for !q.in.IsEmpty() {
			q.out.Push(q.in.Pop())
		}
	}
	return q.out.Pop()
}
